package org.example;

import java.util.*;

public class LCHot100 {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n];
        sum[0] = nums[0];
        for(int i = 1; i < n; i++){
            sum[i] = sum[i-1] + nums[i];
        }
        int ans = 0;
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++){
            //hash.put(sum[i], hash.getOrDefault(sum[i], 0) + 1);
            if(sum[i] == k){
                ans++;
            }
            int target = sum[i] - k;
            ans += hash.getOrDefault(target, 0);
            hash.put(sum[i], hash.getOrDefault(sum[i], 0) + 1);
        }
        return ans;
    }

    class Pair implements Comparable<Pair>{
        public int x;
        public int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pair o) {
            return this.x - o.x;
        }
    }

    public int[][] merge(int[][] intervals) {
        List<Pair> arr = new ArrayList<>();
        for(int[] e : intervals){
            arr.add(new Pair(e[0], e[1]));
        }
        Collections.sort(arr, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.x - o2.x;
            }
        });
        List<int[]> tmp = new ArrayList<>();
        tmp.add(new int[]{arr.get(0).x, arr.get(0).y});
        for(int i = 1; i < arr.size() ; i++){
            if((tmp.get(tmp.size() - 1))[1] < arr.get(i).x){
                tmp.add(new int[]{arr.get(i).x, arr.get(i).y});
            }else{
                int last = tmp.size() - 1;
                tmp.set(last, new int[]{tmp.get(last)[0], Math.max(tmp.get(last)[1], arr.get(i).y)});
            }
        }
        return  tmp.toArray(new int[tmp.size()][]);
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> queue = new LinkedList<>();
        int l = 0;
        int r = 0;
        int tmp = nums[0];
        List<Integer> ans = new ArrayList<>();
        for(; r < nums.length; r++){
            while(!queue.isEmpty() && nums[r] > queue.getLast()){
                queue.removeLast();
            }
//            for(int e : queue){
//                System.out.print(e + " ");
//            }
//            System.out.println();
            queue.addLast(nums[r]);
            if(r >= k){
                ans.add(queue.getFirst());
            }
            if(nums[l++] == queue.getFirst()){
                queue.removeFirst();
            }
        }

       int[] t = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++){
            t[i] = ans.get(i);
        }
        return t;
    }

    private int DFS(TreeNode root, long targetSum){
        int ret = 0;
        if(root == null){
            return 0;
        }
        if(root.val == targetSum){
            ret++;
        }
        ret += DFS(root.left, targetSum - root.val);
        ret += DFS(root.right, targetSum - root.val);
        return ret;
    }
    public int pathSum(TreeNode root, int targetSum) {
        int ret = 0;
        if(root == null){
            return 0;
        }
        ret += DFS(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p , q);
        TreeNode right = lowestCommonAncestor(root.right, p , q);
        if(left != null && right != null){
            return root;
        }
        if(left != null){
            return left;
        }
        if(right != null){
            return right;
        }
        else{
            return null;
        }
    }

    private boolean check(int[] t1, int[] t2){
        for(int i = 0; i < 26; i++){
            if(t1[i] != t2[i]){
                return false;
            }
        }
        return true;
    }

    public List<Integer> findAnagrams(String s, String p) {
        int[] t1 = new int[26];
        for(char e : p.toCharArray()){
            t1[e - 'a']++;
        }
        int l = 0, r = 0;
        List<Integer> ans = new ArrayList<>();
        int[] t2 = new int[26];
        for(; r < s.length(); r++){
            t2[s.charAt(r) - 'a']++;

            if(r >= p.length() - 1){
                if(check(t1, t2)){
                    ans.add(l);
                }
                t2[s.charAt(l++) - 'a']--;
            }
        }
        return ans;
    }

    public int maxProduct(int[] nums) {
        int[][] dp = new int[nums.length][2];
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        int ans = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i][0] = Math.max(Math.max(dp[i-1][0] * nums[i], nums[i]), dp[i-1][1] * nums[i]);
            dp[i][1] = Math.min(Math.min(dp[i-1][0] * nums[i], nums[i]), dp[i-1][1] * nums[i]);
            ans = Math.max(ans, dp[i][0]);
        }
        return ans;
    }

    private boolean DFS(char[][] board, char[] arr, int index, int x, int y){
        if(x < 0 || y < 0 || x >= board.length || y >= board[0].length){
            return false;
        }

        if(index >= arr.length){
            //System.out.println(board[x][y]);
            //System.out.print(x + "," + y);
            return true;
        }

        if(board[x][y] == arr[index]){
            char tmp = board[x][y];
            board[x][y] = 0;
            if(DFS(board, arr, index + 1, x - 1,y)){
                return true;
            }
            if(DFS(board, arr, index + 1, x + 1,y) ){
                return true;
            }
            if(DFS(board, arr, index + 1, x,y + 1)){
                return true;
            }
            if(DFS(board, arr, index + 1, x,y - 1)){
                return true;
            }
            board[x][y] = tmp;
        }
        return false;
    }

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        char[] arr = word.toCharArray();
        if(m == 1 && n == 1 && word.length() == 1){
            return arr[0] == board[0][0];
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(DFS(board, arr, 0, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
}
